package com.leo.ali;

import java.util.*;

/**
 *
 * @author xuexiaolei
 * @version 2018年03月04日
 */
public class Main {
    /** 请完成下面这个函数，实现题目要求的功能 **/
    /** 当然，你也可以不按照这个模板来作答，完全按照自己的想法来 ^-^  **/
    public static void main(String[] args) {

        List<Integer> order = new ArrayList<Integer>();
        Map<String, List<Integer>> boms = new HashMap<String, List<Integer>>();

//        Scanner in = new Scanner(System.in);
//        String line = in.nextLine();
//
//        Integer n = Integer.parseInt(line.split(",")[0]);//n个商品
//        Integer m = Integer.parseInt(line.split(",")[1]);//m个预包方案
//
//        line = in.nextLine();
//        String[] itemCnt = line.split(",");   //商品1个数，商品2个数，。。。，商品n个数
//        for(int i = 0; i < n ; i++){
//            order.add(Integer.parseInt(itemCnt[i]));
//        }
//
//        for(int i = 0; i < m; i++){
//            line = in.nextLine();
//            String[] bomInput = line.split(",");
//            List<Integer> bomDetail = new ArrayList<Integer>();
//
//            for(int j = 1; j <= n; j++ ){
//                bomDetail.add(Integer.parseInt(bomInput[j]));
//            }
//            boms.put(bomInput[0], bomDetail);
//        }
//        in.close();

        order.add(2); order.add(3); order.add(1);
        boms.put("bom1", Arrays.asList(2,1,1));
        boms.put("bom2", Arrays.asList(1,1,0));
        boms.put("bom3", Arrays.asList(0,1,1));

        Map<String, Integer> res = resolve(order, boms);

        System.out.println("match result:");
        for(String key : res.keySet()){
            System.out.println(key+"*"+res.get(key));
        }
    }

    // write your code here
    public static Map<String, Integer> resolve(List<Integer> order, Map<String, List<Integer>> boms) {
        Map<String, Integer> res = new HashMap<>();
        Map<String, Integer> lres = new HashMap<>();
        resolve(order, boms, 0, res, new int[]{order.size()}, lres);
        return lres;
    }

    /**
     * 回溯法调用吧，暂时想不出好的策略
     * @param order      各个产品剩余生数量
     * @param boms      组合的内容
     * @param i         考虑第i个产品
     * @param res       临时结果
     * @param lorderCount       最优结果的剩余产品种类数
     * @param lres              最优结果
     */
    private static void resolve(List<Integer> order, Map<String, List<Integer>> boms, int i, Map<String, Integer> res, int[] lorderCount, Map<String, Integer> lres){
        String key = "bom"+(i+1);
        if (i < order.size()){
            if (couldInsert(order, boms, i)){//如果可以放入当前
                List<Integer> bomi = boms.get(key);
                //产品剩余量得减少
                for (int j = 0; j < bomi.size(); j++) {
                    order.set(j, order.get(j)-bomi.get(j));
                }
                //结果处理
                if (res.containsKey(key)){
                    res.put(key, res.get(key)+1);
                }else {
                    res.put(key, 1);
                }
                //判断是否比最优结果更优
                int stillCount = 0;
                for (int j = 0; j < order.size(); j++) {
                    if (order.get(j) != 0){ stillCount++;}
                }
                if (stillCount < lorderCount[0]) {
                    lorderCount[0]=stillCount;
                    lres.clear();
                    for (Map.Entry<String, Integer> entry : res.entrySet()){
                        lres.put(entry.getKey(), entry.getValue());
                    }
                }else if (stillCount == lorderCount[0]){
                    if (res.size() < lres.size()) {
                        lres.clear();
                        for (Map.Entry<String, Integer> entry : res.entrySet()) {
                            lres.put(entry.getKey(), entry.getValue());
                        }
                    }
                }

                resolve(order, boms, i, res, lorderCount, lres);

                //把原来的加回去
                for (int j = 0; j < bomi.size(); j++) {
                    order.set(j, order.get(j)+bomi.get(j));
                }
                Integer iii = res.get(key);
                if (iii == 1){
                    res.remove(key);
                }else {
                    res.put(key, iii-1);
                }
            }

            resolve(order, boms, i+1, res, lorderCount, lres);//不放当前boms
        }
    }

    /**
     * 第i个boms能否放进去1个，放进去则order的减去数量，放不进去则不减
     * @param order
     * @param boms
     * @param i
     * @return
     */
    private static boolean couldInsert(List<Integer> order, Map<String, List<Integer>> boms, int i){
        List<Integer> bomi = boms.get("bom"+(i+1));
        for (int j = 0; j < bomi.size(); j++) {
            if (bomi.get(j) > order.get(j)){ return false; }
        }
        return true;
    }
}
